/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root)  return true;
        /*
        如果一颗二叉树和它的镜像一样，那么它就是对称的;
        先同时传入主左右子树节点，比较他们是否相等;
        之后比较两个传入节点的相反方向节点
		即：定义一个与前序遍历对称的方法：先遍历根节点，之后是右结点，之后才是左节点，必须考虑节点为NULL的情况；
		若自定义前序遍历和自定义前序遍历对称算法遍历结果完全一致，则该二叉树对称
        */
        return isSame(root->left, root->right);
    }

    //若传入节点同时为空或值相等，则返回ture
    bool isSame(TreeNode* rootLeft, TreeNode* rootRight){
        if(!rootLeft && !rootRight)  return true;
        else if(!rootLeft || !rootRight)  return false;  //两节点仅有一个为空
        
        if(rootLeft->val == rootRight->val){
            return isSame(rootLeft->left, rootRight->right) && isSame(rootLeft->right, rootRight->left);
        }else{
            return false;
        }
    }
};